/**
 * @short Find the dominators in the control flow graph.
 */

#ifndef _COMPILATION_DOMINATION_TASK_H_
#define _COMPILATION_DOMINATION_TASK_H_

#include <compilation/task/Task.h>
#include <compilation/task/Handler.h>
#include <compilation/task/Propagator.h>

#include <compilation/Function.h>


// DominationTask and DominationAgenda.
namespace compilation
{

/**
 * @brief Find the dominator of an instruction regarding
 *        the previous covered instructions.
 */
class DominationTask
    : public VirtualTask
{
  /// The current domination height in the domination tree.
  int m_height;

  /// The previous visited instruction.
  VirtualInstruction* m_previous;

public:

  DominationTask(const VirtualInstruction& instruction)
    : m_height(1), m_previous(nullptr)
  { setInstruction(instruction); }

  DominationTask(const DominationTask& source)
    : VirtualTask(source), m_height(source.m_height) , m_previous(nullptr) {}

  /// Change the domination height.
  void setHeight(int newHeight)
  { assert(newHeight < m_height); m_height = newHeight; }

  int getHeight(void) const
  { return m_height; }

  VirtualInstruction* getPrevious(void) const
  { return m_previous; }

  VirtualInstruction* findDominatorWith(VirtualInstruction& instruction) const;

  virtual void applyOn(VirtualInstruction& instruction, VirtualAgenda& continuations);

  virtual VirtualTask* clone(void) const;

  virtual bool mergeWith(VirtualTask& vtSource);
};

/**
 * @brief Cover all the control flow graph to find the dominators.
 */
class DominationAgenda
    : public VirtualAgenda
{
public:

  typedef DominationTask Task;

  typedef InstructionVisitor<
  void, DominationTask&, DominationAgenda&, WorkListReusability&>
  instruction_handler_visitor_type;

  typedef InstructionVisitor<
  bool, DominationTask&, DominationAgenda&, WorkListReusability&>
  instruction_propagator_visitor_type;

  instruction_handler_visitor_type const& handleInstruction;
  instruction_propagator_visitor_type const& propagateOnUnmarked;

  DominationAgenda(
      instruction_handler_visitor_type const& instruction_handler,
      instruction_propagator_visitor_type const& instruction_propagator,
      const Function& function)
    : handleInstruction(instruction_handler)
    , propagateOnUnmarked(instruction_propagator)
  { addNewAsFirst(new DominationTask(function.getFirstInstruction())); }

  virtual void markInstructionWith(VirtualInstruction& instruction, VirtualTask& task) {}
};

} // compilation

// DominationHandler.
namespace compilation
{

template <InstructionType _Type>
struct DominationHandler
    : public InstructionHandler<_Type, DominationTask, DominationAgenda>
{
  void operator ()(
      VirtualInstruction* instr,
      DominationTask& task,
      DominationAgenda& continuations,
      WorkListReusability& reuse)
  {
    InstructionHandler<_Type, DominationTask, DominationAgenda>
        ::operator ()(instr,task,continuations,reuse);
  }
};

template <>
struct DominationHandler<TLabel>
    : public InstructionHandler<TLabel, DominationTask, DominationAgenda>
{
  void operator ()(
      VirtualInstruction* instr,
      DominationTask& task,
      DominationAgenda& continuations,
      WorkListReusability& reuse)
  {
    LabelInstruction* ins = instruction_cast<TLabel>(instr);

    if (!ins->getSDominator())
      ins->setSDominator(task.getPrevious());
    else
    {
      VirtualInstruction* newDominator =
          task.findDominatorWith(*ins->getSDominator());

      if (newDominator == ins->getSDominator()) return;
      task.setHeight(newDominator->getDominationHeight() + 1);
      ins->setSDominator(newDominator);
    }

    base_handler::operator ()(instr,task,continuations,reuse);
  }
};

} // compilation

#endif // _COMPILATION_DOMINATION_TASK_H_
